package wtx.leetcode;

import java.util.HashMap;
import java.util.Map;


/**
 * 给你一个仅由大写英文字母组成的字符串，你可以将任意位置上的字符替换成另外的字符，总共可最多替换 k 次。在执行上述操作后，找到包含重复字母的最长子串的长度。
 * 
 * 注意: 字符串长度 和 k 不会超过 104。
 * 
 * 示例 1:
 * 
 * 输入: s = "ABAB", k = 2
 * 
 * 输出: 4
 * 
 * 解释: 用两个'A'替换为两个'B',反之亦然。 
 * 
 * 示例 2:
 * 
 * 输入: s = "AABABBA", k = 1
 * 
 * 输出: 4
 *  解释: 将中间的一个
 * A'替换为'B',字符串变为 "AABBBBA"。 子串 "BBBB" 有最长重复字母, 答案为 4。
 * reference: https://leetcode-cn.com/problems/longest-repeating-character-replacement/
 * =========================== Solution ===========================
 * comments: 这种解法一般人不可能在面试当场推出来。所以一般的思路是，
 * 先给出一个效率还可以的（甚至是暴力求解）的算法，
 * 然后不断构造case，这样才能观察出一些规律。(后来觉得牛人应该还是可以想到的。)
 * 
 * 思路 滑动窗口核心的，窗口左右边界如何增减，当满足条件时右边增，不满足条件时左边减，如此变化窗口大小，得出当前窗口的解，
 * 并往前移动窗口直至移动到队列尾部扫描一遍，问题得到最终解决。 对应于此题，滑动窗口右边不断增长，需要考虑满足增长的条件，
 * 以及不满足条件时，窗口左边如何减。 这个条件是“right - left + 1 - max > k“ 
 * 当前需要替换的字符数大于k 否则,窗口左边收缩 左边如何减：dict[s[i++]]--;，左边元素移动一个，计数减一 
 * 你会发现max不需要相应减少，假设后面一个窗口中的most-freq-char的cnt（即maxCnt）比原来少，
 * 那么它肯定不是最优解。
 * 因为算法只有在j-i+1-maxCnt > k的时候，才会左移left指针，在此之前，肯定已经找到了一个状态，即
 * j - i + 1 = k + maxCnt,
 * 所以，即使你更新了maxCnt，它所在的区间也不是最优解。还不如不更新。
 * 
#define MAX(x, y) ((x)>(y) ? (x) : (y))

int characterReplacement(char * s, int k){
    int i, j, maxCnt, res;
    int len = strlen(s);
    int dict[128] = {0};
    
    for (i=j=res=maxCnt=0; j<len; j++) {
        char ch = s[j];        
        
        dict[ch]++;
        maxCnt = MAX(maxCnt, dict[ch]);   
        if (j-i+1-maxCnt > k)
            dict[s[i++]]--;        
        res = MAX(j-i+1, res);  
    }
    
    return res;
} 
 */
public class HelloWorld {
  class RangeInfo {
    int len;
    int start;
    int holes; // 从end（即start+len）位置到当前位置的其他字符个数
    int useQuota; // 从start到end中的其他字符个数
  }
  
  private RangeInfo initOneCharInfo(char a, int k, boolean match) {
    RangeInfo info = new RangeInfo();
    info.start = 0;
    info.len = match ? 1 : (
      k > 0 ? 1 : 0
    );
    info.holes = 0;
    info.useQuota = match ? 0 : (
      k > 0 ? 1 : 0
    );
    return info;
  }
  
  public int characterReplacement(String s, int k) {
    if (k < 0 || s == null || s.length() == 0) {
      return 0;
    }
    if (k > s.length()) {
      return k;
    }

    final int DictLen = 'Z' - 'A' + 1;
    Map<Character, RangeInfo> charMap = new HashMap<>();
    final int LenStr = s.length();
    final char firstChar = s.charAt(0);
    for (int i = 0; i < LenStr; ++i) {
      char a = s.charAt(i);
      charMap.computeIfAbsent(a, key -> initOneCharInfo(key, k, a == firstChar));
      if (charMap.size() >= DictLen) {
        break;
      }
    }
    for (int i = 1; i < LenStr; ++i) {
      final char a = s.charAt(i);
      // 处理当前字符
      RangeInfo info = charMap.get(a);
      if (info.useQuota + info.holes <= k) {
        // 需要处理len == 0的特殊情况。此时表示前面的range无效
        if (info.len == 0) {
          info.start = i;
          info.len = 1;
          info.holes = 0;
          info.useQuota = 0;
        } else {
          // 可以无条件增加
          info.len = i - info.start + 1;
          info.useQuota += info.holes;
          info.holes = 0;
        }
      } else {
        // 寻找合适的hole，包含当前字符
        int start = info.start;
        int useQuota = info.holes;
        if (useQuota <= k) {
          start = start + info.len;
        } else {
          start = i;
          useQuota = 0;
        }
        int newlen = i - start + 1;
        for (int j = start - 1; j >= 0; --j) {
          if (s.charAt(i) == s.charAt(j)) {
            newlen += 1;
            start = j;
          } else {
            if (useQuota >= k) {
              break;
            } else {
              start = j;
              useQuota += 1;
              newlen += 1;
            }
          }
        }
        if (newlen >= info.len) {
          info.len = newlen;
          info.start = start;
          info.useQuota = useQuota;
          info.holes = 0;
        }
      }
      // 处理其他字符
      for (char ca : charMap.keySet()) {
        if (ca != a) {
          charMap.get(ca).holes += 1;
        }
      }
    }

    // char useChar = 'A';
    RangeInfo maxInfo = null;
    int max = 0;
    for (char ca : charMap.keySet()) {
      RangeInfo info = charMap.get(ca);
      if (info.useQuota < k && info.holes > 0) {
        info.len += Math.min(k - info.useQuota, info.holes);
      }
      if (info.len > max) {
        maxInfo = info;
        max = maxInfo.len;
        // useChar = (char) ('A' + i);
      }
    }
    // System.out.println("use char: [" + useChar + "], start from " + maxInfo.start
    // + ", use quota " + maxInfo.useQuota + ", length = " + max);
    return max;
  }
}
